package com.breeze.sort;

/**
 * 三、插入排序(普通版)
 * 1. 把整体看做一个有序表和无序表，每次从无需表中拿出一个元素选择合适位置插入有序表，比较 length-1次即可排好序
 */
public class InsertionSort implements Sort {
    @Override
    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int index = i;

            // 将第i个数与前面数比较，小则交换
            while (index > 0 && arr[index] < arr[index - 1]) {
                int tmp = arr[index];
                arr[index] = arr[index - 1];
                arr[index - 1] = tmp;
                index--;
            }
        }
    }
}
